食物链 [NOI 2005]
食物链 [NOI 2005]
带权并查集
这题目以前做过，但是好像没做对，今天正好学了带权并查集，才算是恍然大悟。
题目来源: Luogu
分析
在这道题中，我们总共有三种动物，我们可以分别把他们标号为0,1,2,然后在这里，我们规定2吃1,1吃0,0吃2。
然后，作为一道带权并查集的题目，这道题肯定是以并查集为主。其与常规的并查集的不同之处是在操作时多加入一个对权值的判断或者更改操作。我们假设fa[]为记录的"父节点",f[]为其与"父节点"的权值差。
首先，我们来看插入操作。在这里，插入操作分为两种:两种动物为同一物种或捕食关系。我们以较为简单的同一物种为例。在此情况下，我们先判断这两个动物是否在同一集合内——find(x)==find(y)? 若是的话，则直接比较其相对根节点的权值即可，不同的话则是假命题。而当其不在一个集合中时，我们则需要先做一次合并操作，然后再更新一次f[]即可。代码如下： 1
2
3
4
5
6
7
8
9
| int fx = find(x), fy = find(y);
if (fx==fy)
{
trueif ( f[x]!=f[y] )
truetruecnt ++;
}else{
truefa[fx] = fy;
truef[fx] = (f[y] - f[x] + 3) % 3;
}
|
find()操作也类似，代码如下: 1
2
3
4
5
6
7
8
9
10
11
12
13
| int find(int x)
{
trueint fx = fa[x];
trueif (fa[x]!=x)
true{
truetruefa[x] = find(fa[x]);
truetruef[x] = ( f[x] + f[fx] ) % 3;
truetruereturn fa[x];
true}
truereturn x;
}
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include <iostream>
using namespace std;
int fa[50010];
int f[50010];
int find(int x)
{
trueint fx = fa[x];
trueif (fa[x]!=x)
true{
truetruefa[x] = find(fa[x]);
truetruef[x] = ( f[x] + f[fx] ) % 3;
truetruereturn fa[x];
true}
truereturn x;
}
int main()
{
trueint n,T;
truecin >> n >> T;
truefor (int i = 1; i<=n; i++)
true{
truetruefa[i] = i;
truetruef[i] = 0;
true}
trueint cnt = 0;
truewhile (T--)
true{
truetrueint q,x,y;
truetruecin >> q >> x >> y;
truetrueif ( (q==2 && x==y) || (x>n || y>n))
truetrue{
truetruetruecnt ++;
truetruetruecontinue;
truetrue}
truetrueif (q==1)
truetrue{
truetruetrueint fx = find(x), fy = find(y);
truetruetrueif (fx==fy)
truetruetrue{
truetruetruetrueif ( f[x]!=f[y] )
truetruetruetruetruecnt ++;
truetruetrue}else{
truetruetruetruefa[fx] = fy;
truetruetruetruef[fx] = (f[y] - f[x] + 3) % 3;
truetruetrue}
truetrue}else if (q==2)
truetrue{
truetruetrueint fx = find(x), fy = find(y);
truetruetrueif (fx==fy)
truetruetrue{
truetruetruetrueif ( (f[y]-f[x]+3)%3 != 1 )
truetruetruetruetruecnt ++;
truetruetrue}else{
truetruetruetruefa[fx] = fy;
truetruetruetruef[fx] = ( f[y] - f[x] - 1 + 3) % 3;
truetruetrue}
truetrue}
true}
truecout << cnt << endl;
}
|